/**
 * 
 */
package leetCode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author zhongfang
 *
 */
public class MaximumProductofThreeNumbers {
    public static int maximumProduct(int[] nums) {
    	PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(2, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2-o1;
			}
		});
    	PriorityQueue<Integer> priorityQueue2=new PriorityQueue<>(3);
    	
    	for (int i = 0; i < nums.length; i++) {
			if(priorityQueue.size()<2){
				priorityQueue.add(nums[i]);
			}else if (nums[i]<priorityQueue.peek()) {
				priorityQueue.remove();
				priorityQueue.add(nums[i]);
			}
			
			if(priorityQueue2.size()<3){
				priorityQueue2.add(nums[i]);
			}else if (nums[i]>priorityQueue2.peek()) {
				priorityQueue2.remove();
				priorityQueue2.add(nums[i]);
			}
		}
    	
		return Math.max(priorityQueue2.poll()*priorityQueue2.poll(), priorityQueue.poll()*priorityQueue.poll())*priorityQueue2.poll();
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] nums={-1,-2,-3};
		System.out.println(maximumProduct(nums));
	}

}
